package leetcode.code0127;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.Set;

/**
 * 执行用时：30 ms, 在所有 Java 提交中击败了78.69%的用户
 *
 * 内存消耗：46.8 MB, 在所有 Java 提交中击败了7.80%的用户
 *
 * 通过测试用例：49 / 49
 */
public class Solution3 extends Solution127 {

	Map<String, List<String>> ways;

	@Override
	public int ladderLength(String beginWord, String endWord, List<String> wordList) {
		if (!wordList.contains(endWord)) {
			return 0;
		}
		ways = new HashMap<>();// 所有路径<原词,通配词列表> <通配词,原词列表>
		this.findWays(wordList);// 初始化ways
		Set<String> counts = new HashSet<>();//
		Queue<String> q = new LinkedList<>();
		this.init(q, counts, beginWord);//
		int ans = 1;
		while (!q.isEmpty()) {
			int size = q.size();
			ans += 1;
			while (size > 0) {
				String from = q.poll();
				if (from.equals(endWord)) {
					return ans;
				}
				this.move(q, counts, from);
				size--;
			}
		}
		return 0;
	}

	private void move(Queue<String> q, Set<String> counts, String from) {
		List<String> links = ways.get(from);
		for (String link : links) {
			List<String> tos = ways.get(link);
			for (String to : tos) {
				if (!counts.contains(to)) {
					counts.add(to);
					q.add(to);
				}
			}
		}
	}

	private void init(Queue<String> q, Set<String> counts, String beginWord) {
		char[] cur = beginWord.toCharArray();
		for (int i = 0; i < beginWord.length(); i++) {
			char c = cur[i];
			cur[i] = '*';
			String link = new String(cur);
			if (ways.containsKey(link)) {
				for (String to : ways.get(link)) {
					if (!counts.contains(to)) {
						counts.add(to);
						q.add(to);
					}
				}
			}
			cur[i] = c;
		}
	}

	private void findWays(List<String> wordList) {
		for (String string : wordList) {
			char[] cur = string.toCharArray();
			for (int i = 0; i < cur.length; i++) {// 原词的每一位变成通配词
				char c = cur[i];
				cur[i] = '*';// 变更i位
				this.add2ways(string, new String(cur));// 建立原词和通配词的路
				cur[i] = c;// 回溯
			}
		}
	}

	private void add2ways(String str1, String str2) {
		List<String> list = ways.getOrDefault(str1, new ArrayList<>());
		list.add(str2);
		ways.put(str1, list);// 原词列表中添加一个通配词
		list = ways.getOrDefault(str2, new ArrayList<>());
		list.add(str1);
		ways.put(str2, list);// 通配词列表中添加一个原词
	}

	public static void main(String[] args) {
		Solution3 so = new Solution3();
		so.debug1();
		so.debug2();
		so.debug5();
		so.debug3();

	}

}
